/*
 * @lc app=leetcode.cn id=743 lang=golang
 * @lcpr version=30119
 *
 * [743] 网络延迟时间
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start

type Node struct {
	Target int
	Weight int
}

func networkDelayTime(times [][]int, n int, k int) int {
	edges := make([][]Node, n)
	for i := 0; i < n; i++ {
		edges[i] = make([]Node, 0)
	}
	for i := 0; i < len(times); i++ {
		edges[times[i][0]-1] = append(edges[times[i][0]-1], Node{Target: times[i][1] - 1, Weight: times[i][2]})
	}

	costs := solve(edges, k-1)
	ans := maxInArray(costs)
	if ans == math.MaxInt32 {
		return -1
	}
	return ans
}

func solve(edges [][]Node, src int) []int {
	n := len(edges)
	costs := make([]int, n)
	for i := 0; i < n; i++ {
		costs[i] = math.MaxInt32
	}
	costs[src] = 0
	for i := 0; i < n; i++ {
		for j := 0; j < len(edges[i]); j++ {
			if costs[edges[i][j].Target] > costs[i]+edges[i][j].Weight {
				costs[edges[i][j].Target] = costs[i] + edges[i][j].Weight
				dfs(edges, edges[i][j].Target, costs)
			}
		}
	}
	return costs
}

func dfs(edges [][]Node, src int, costs []int) {
	for _, e := range edges[src] {
		if costs[e.Target] > costs[src]+e.Weight {
			costs[e.Target] = costs[src] + e.Weight
			dfs(edges, e.Target, costs)
		}
	}
}

func maxInArray(arr []int) int {
	max := arr[0]
	for _, value := range arr {
		if value > max {
			max = value
		}
	}
	return max
}

// @lc code=end

/*
// @lcpr case=start
// [[2,1,1],[2,3,1],[3,4,1]]\n4\n2\n
// @lcpr case=end

// @lcpr case=start
// [[1,2,1]]\n2\n1\n
// @lcpr case=end

// @lcpr case=start
// [[1,2,1]]\n2\n2\n
// @lcpr case=end

*/

